package com.aqie.arithmetic.sort;

/**
 * 自底向上的归并排序
 */
public class MergeBU extends SortTest{
    private static Comparable[] aux;

    public static void merge(Comparable[] a, int l, int mid, int h){
        int i = l, j = mid + 1;
        for (int k = l; k <= h; k++){
            aux[k] = a[k];
        }

        for (int k = l; k <= h; k++){
            if (i > mid) a[k] = aux[j++];
            else if (j > h) a[k] = aux[i++];
            else if(less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    @Override
    public void sort(Comparable[] a) {
        // 进行lgN 次两两归并
        int N = a.length;
        aux = new Comparable[N];
        // sz 子数组大小 l:子数组索引
        for (int sz = 1; sz < N; sz = sz + sz){
            for (int l = 0; l < N - sz; l += sz+sz){
                merge(a, l, l+sz -1, Math.min(l + sz + sz -1, N -1));
            }
        }
    }

    public static void main(String[] args) {
        new MergeBU().process(10000);
    }
}
